package priv.conceit.study.leetcode.simple.official;


import java.util.LinkedList;
import java.util.Objects;
import java.util.Queue;

/**
 * 编号104
 * 二叉树的最大深度
 * <a href="https://leetcode-cn.com/problems/maximum-depth-of-binary-tree/"></a>
 * <p>
 * 给定一个二叉树，找出其最大深度。
 * 二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
 * 说明: 叶子节点是指没有子节点的节点。
 * <p>
 * 示例：
 * 给定二叉树 [3,9,20,null,null,15,7]，
 *     3
 *    / \
 *   9  20
 *   /  \
 *  15   7
 * <p>
 * 返回它的最大深度 3
 *
 * @author Conceit
 * @since 1.0.0, 2019/7/16
 */
public class MaximumDepthOfBinaryTree {

	public static void main(String[] args) {

	}

	/**
	 * 非递归
	 * bfs广度优先
	 *
	 * 使用队列
	 * 先入先出
	 *
	 * 采用二叉树的层序遍历的思想。
	 * 我们需要遍历每层，每遍历完一层则将depth进行加一的操作。
	 * 这个问题的关键在于如何知道每层是否遍历完了，
	 * 我们可以定义一个初始变量size，然后将size和每层的进入队列的节点的size进行比较，判断是否遍历完这个层的最后一个节点。
	 *
	 * @param root
	 * @return
	 */
	public int bfs(TreeNode root) {
		int depth=0;
		int count=0;
		if(Objects.isNull(root)){
			return depth;
		}
		Queue<TreeNode> queue=new LinkedList<>();
		queue.add(root);
		while (!queue.isEmpty()){
			//每遍历一层+1
			depth++;

			//上一层的节点数
			int size = queue.size();
			for(int i=0;i<size;i++){
				//每一层的有效节点数
				count++;
				//检索并删除此列表的头部(第一个元素)。
				TreeNode curTreeNode=queue.poll();
				if(Objects.nonNull(curTreeNode.left)){
					queue.add(curTreeNode.left);
				}
				if(Objects.nonNull(curTreeNode.right)){
					queue.add(curTreeNode.right);
				}

			}

		}
		System.out.println("count-->"+count);
		return depth;
	}

	/**
	 * 递归
	 * 如果入参为null，那么该层返回0，不纳入计算
	 * 不为null则分别 将左右节点纳入计算，返回每次需要加1
	 *
	 * @param root
	 * @return
	 */
	public int recursive (TreeNode root,int depth){
		if(Objects.nonNull(root)){
			int left=recursive(root.left, depth);
			int right=recursive(root.right, depth);
			return Math.max(left,right)+1;
		}
		return 0;

	}

	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode(int x) {
			val = x;
		}
	}
}
